home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / de / comm / isdn / 787 < prev    next >
Text File  |  1996-08-06  |  1KB  |  33 lines
  1. Newsgroups: de.comm.isdn
  2. Path: gandalf.ruhr.de!not-for-mail
  3. From: dirk@gandalf.ruhr.de (Dirk Kruschewski)
  4. Subject: Re: kleinste Strecke?
  5. Message-ID: <1a7cc$16339.27c@gandalf.ruhr.de>
  6. Date: Wed, 10 Jan 1996 21:03:57 GMT
  7. Distribution: world
  8. Organization: Private site running Windows NT 3.51
  9. References: <4ctre5$jds@ux-01.bg.bib.de> <4d0fk2$gog@gwdu19.gwdg.de>
  10. X-Newsreader: News for Windows NT X1.0-75
  11.  
  12. In article <4d0fk2$gog@gwdu19.gwdg.de>
  13. ptillma@gwdu19.gwdg.de (Peter Tillmann ) wrote:
  14.  
  15. > Moehlmann Peter (w3f5mo@ux-01.bg.bib.de.) thought and said:
  16. > 
  17. > :>Wir brauchen einen Algorithmus, der uns zu n StΣdten die optimale Vernetzung gibt.
  18. > :>Das heisst, die Summe aller Teilstrecken soll minimal sein. Die StΣdte brauchen nur 1 mal
  19. > :>mit einer anderen Stadt verbunden sein.
  20. > 
  21. > Und was hat das mit ISDN zu tun?
  22. Frag ich mich auch...
  23. > Steht uebrigens in jedem Lehrbuch zum Thema Operations Research unter
  24. > Traveling salesman Problem und ist np-hart (oder wie hiess das noch).
  25.  
  26. Nix Traveling Salesman. Graphenproblem -> Minimaler Spannbaum ->
  27. -> Algorithmus von Kruskal
  28. TSP ist im ⁿbrigen NP-vollstΣndig.
  29.  
  30. --
  31. cu, Dirk
  32.  
  33.